/**
 * 
 */
package fanalg;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Set;


/**
 * @author Tomasz Werszko
 * Class for parsing Blif code and storing the circuit
 */
public class Circuit {
	
	/**
	 * List of primary inputs of the circuit
	 */
	protected ArrayList<String> primaryInputs = new ArrayList<String>();
	/**
	 * List of primary outputs of the circuit
	 */
	protected ArrayList<String> primaryOutputs = new ArrayList<String>();
	protected String modelName = "";
	/**
	 * List of gates
	 */
	protected Hashtable<String, CircuitEntity> entities = new Hashtable<String, CircuitEntity>();
	/**
	 * connection net
	 */
	protected Hashtable<CircuitEntity, List<String>> connectionNet = new Hashtable<CircuitEntity, List<String>>();
	
	protected ArrayList<String> dfrontier = new ArrayList<String>();
	protected CircuitEntity faulty;
	protected LogicSystem fault;
	protected CircuitEntity gut;
	
	protected DecisionTree tree;
	protected LogicSystem primaryObj = LogicSystem.X;
	
	/**
	 * Constructor which parses Blif code from file
	 * @param fileName - name of a file to be parsed
	 */
	public Circuit(String fileName) throws Exception{
	    this.parse(fileName);
	    //constructing connection matrix
	    this.contructConnectionMatrix();
	}
	
	//verbose
	public boolean verbose = false;
	
	/**
	 * Returns list of primary inputs
	 */
	public ArrayList<String> getPrimatyInputs(){
		return this.primaryInputs;
	}
	
	/**
	 * Returns list of primary outputs
	 */
	public ArrayList<String> getPrimatyOutputs(){
		return this.primaryOutputs;
	}
	
	/**
	 * Returns model name
	 * @return
	 */
	public String getModelName(){
		return this.modelName;
	}
	/**
	 * Returns list of gates
	 * @return
	 */
	public Hashtable<String, CircuitEntity> getEntities(){
		return this.entities;
	}
	
	/**
	 * Get the gate
	 * @param name - name of the gate
	 */
	public CircuitEntity getEntity(String name){
		return this.entities.get(name);
	}
	
	/**
	 * Returns the connection net
	 */
	public Hashtable<CircuitEntity, List<String>> getConnectionNet(){
		return this.connectionNet;
	}
	
	/**
	 * 
	 * @param fileName
	 * @throws Exception
	 */
	public void parse(String fileName) throws Exception{
		//StringBuffer sb = new StringBuffer();
	    BufferedReader in = new BufferedReader(new FileReader(fileName));
	    
	    String fName = fileName.substring(fileName.lastIndexOf(File.separator)+1, fileName.length());
	    
	    //clearing structure of the object
	    this.modelName = "";
	    this.entities = new Hashtable<String, CircuitEntity>();
	    this.primaryInputs = new ArrayList<String>();
	    this.primaryOutputs = new ArrayList<String>();
	    
	    //temporary variables
	    String s, currentOp = "", tmp = " ";
	    Gate lastGate = null;
	    ArrayList<String> gateNames = new ArrayList<String>();
	    int line = 0;
	    int lastGateInputs = 0;
	    while((s = in.readLine()) != null || !tmp.equals("")){
	    	//if line breaking occurred
	    	if(!tmp.equals("")){
	    		if(s == null){
	    			s = tmp;
	    		}else{
	    			s = tmp + s;
	    		}
	    		tmp = "";
	    	}
	    	//eliminating comments
	    	if(s.contains("#")){
	    		s = s.substring(0, s.indexOf("#"));
	    	}
	    	s = s.trim();
	    	
	    	line++;
	    	
	    	//line breaking
	    	if(s.length() > 0 && s.charAt(s.length()-1) == '\\'){
	    		tmp = s.substring(0, s.length()-1);
	    		continue;
	    	}
	    	
	    	//model name
	    	if(s.contains(".model")){
	    		currentOp = "model";
	    		s = s.replace(".model", "");
	    		s = s.trim();
	    		if(this.modelName == ""){
	    			this.modelName = s;
	    		}else{
	    			throw new ParserException(line, "Only one model allowed.");
	    		}
	    	}
	    	//inputs
	    	else if(s.contains(".inputs")){
	    		currentOp = "inputs";
	    		s = s.replace(".inputs", "");
	    		s = s.trim();
	    		String[] inputs = s.split(" ");
	    		for(int i = 0; i < inputs.length; i++){
	    			if(inputs[i].contains("#")){
	    				throw new ParserException(line, "Incorrect name of the input.");
	    			}
	    			if(this.primaryInputs.contains(inputs[i].trim())){
	    				throw new ParserException(line, "Duplicated input " + inputs[i].trim() + ".");
	    			}else{
	    				Input input = new Input(inputs[i].trim());
	    				this.primaryInputs.add(inputs[i].trim());
	    				if(this.entities.containsKey(inputs[i].trim())){
	    					throw new ParserException(line, "Duplicated " + inputs[i].trim() + ".");
	    				}
	    				this.entities.put(inputs[i].trim(), input);
	    				this.connectionNet.put(input, new ArrayList<String>());
	    			}
	    		}
	    	}
	    	//outputs
	    	else if(s.contains(".outputs")){
	    		currentOp = "outputs";
	    		s = s.replace(".outputs", "");
	    		s = s.trim();
	    		String[] outputs = s.split(" ");
	    		for(int i = 0; i < outputs.length; i++){
	    			if(outputs[i].contains("#")){
	    				throw new ParserException(line, "Incorrect name of the output.");
	    			}
	    			if(this.primaryOutputs.contains(outputs[i].trim())){
	    				throw new ParserException(line);
	    			}else{
	    				this.primaryOutputs.add(outputs[i].trim());
	    			}
	    		}
	    	}
	    	//end
	    	else if(s.contains(".end")){
	    		//if no model name yet
	    		if(this.modelName.equals("")){
	    			this.modelName = fName;
	    		}
	    		break;
	    	}
	    	//gates
	    	else if(s.contains(".names")){
	    		currentOp = "names";
	    		s = s.replace(".names", "");
	    		s = s.trim();
	    		String[] names = s.split(" ");
	    		if(names.length < 2 || gateNames.contains(names[names.length-1])){
	    			throw new ParserException(line);
	    		}else{
	    			String [] inputs = new String[names.length -1];
	    			for(int i = 0; i < inputs.length; i++){
	    				inputs[i] = names[i];
	    			}
	    			Gate gate = new Gate(inputs, names[names.length-1]);
	    			lastGate = gate;
	    			lastGateInputs = inputs.length;
	    			//System.out.println(x)
	    			if(this.entities.containsKey(names[names.length-1])){
	    				throw new ParserException(line, "Duplicated gate " + names[names.length-1]);
	    			}else{
	    				this.entities.put(names[names.length-1], gate);
	    				this.connectionNet.put(gate, new ArrayList<String>());
	    			}
	    		}
	    	//other operation
	    	}else if(s.length() > 0 && s.charAt(0) == '.'){
	    		s = s.substring(1);
	    		String str[] = s.split(" ");
	    		if(str[0] != null){
	    			currentOp = str[0];
	    		}
	    	
	    	//getting a gate
	    	}else if(currentOp == "names"){
	    		String[] str = s.split(" ");
	    		//single 1 or 0 at line
	    		if(str.length == 1 && (s.equals("0") || s.equals("1"))){
	    			if(s.equals("1")){
	    				for(int i = 0; i < lastGate.truthVector.length; i++){
	    					lastGate.truthVector[i] = true;
	    				}
	    			}else if(s.equals("0")){
	    				for(int i = 0; i < lastGate.truthVector.length; i++){
	    					lastGate.truthVector[i] = false;
	    				}
	    			}else{
	    				throw new ParserException(line);
	    			}
	    		// xx..x x at line
	    		}else if(str.length == 2){
	    			str[0] = str[0].trim();
	    			str[1] = str[1].trim();
	    			
	    			//checking output
	    			boolean combination = false;
	    			if(str[1].equals("0")){
	    				combination = false;
	    			}else if(str[1].equals("1")){
	    				combination = true;
	    			}else{
	    				throw new ParserException(line);
	    			}
	    			
	    			if(str[0].length() != lastGateInputs){
	    				System.out.println(str[0].length());
	    				System.out.println(lastGateInputs);
	    				throw new ParserException(line, "Incorrect number of inputs");
	    			}
	    			
	    			//checking input
	    			for(int i = 0; i < str[0].length(); i++){
	    				if(str[0].charAt(i) != '0' && str[0].charAt(i) != '1' && str[0].charAt(i) != '-'){
	    					throw new ParserException(line);
	    				}
	    			}
	    			Hashtable<String, Boolean> list = new Hashtable<String, Boolean>();
	    			list.put(str[0], new Boolean(combination));
	    			for(int i = 0; i < str[0].length(); i++){
	    				Iterator<String> iterator = list.keySet().iterator();
	    				ArrayList<String> tmpList = new ArrayList<String>();
	    				while(iterator.hasNext()){
	    					String string = iterator.next();
	    					if(string.contains("-")){
	    						tmpList.add(string);
	    					}
	    				}
	    				for(int j = 0; j < tmpList.size(); j++){
	    					String string = tmpList.get(j);
	    					Boolean comb = list.get(string);
	    					list.remove(string);
	    					list.put(string.replaceFirst("-", "0"), comb);
	    					list.put(string.replaceFirst("-", "1"), comb);
	    				}
	    			}
	    			//setting truth table
	    			Iterator<String> iterator = list.keySet().iterator();
    				while(iterator.hasNext()){
    					String string = iterator.next();
    					Boolean comb = list.get(string);
    					lastGate.truthVector[Integer.parseInt(string, 2)] = comb;
    				}
	    		//if line is wrong
	    		}else if(str[0].length() > 0){
	    			throw new ParserException(line);
	    		}
	    	}else if(s.length() > 0){
	    		throw new ParserException(line);
	    	}
	    	
	    }
	    in.close();
	    //if no model name yet
		if(this.modelName.equals("")){
			this.modelName = fName;
		}
	    
	    //checking for unallowed situations
	    Iterator<String> iterator = this.entities.keySet().iterator();
	    while(iterator.hasNext()){
	    	String string = iterator.next();
	    	if(this.primaryInputs.contains(string) && this.entities.get(string) instanceof Gate){
	    		throw new ParserException("Gate cannot have the same name as one of the inputs");
	    	}
	    	CircuitEntity entity = this.entities.get(string);
	    	for(int i = 0; i < entity.inputs.length; i++){
	    		if(this.primaryOutputs.contains(entity.inputs[i])){
	    			throw new ParserException("Gate " + entity.output + " has incorrect input.");
	    		}
	    	}
	    }
	    iterator = this.primaryOutputs.iterator();
	    while(iterator.hasNext()){
	    	String string = iterator.next();
	    	if(!(this.entities.containsKey(string) || this.primaryInputs.contains(string))){
	    		throw new ParserException("Output " + string + " undefined");
	    	}
	    }
	    
	    //no inputs or outputs (normally it should be only a warning)
	    if(this.primaryInputs.size() == 0){
	    	throw new ParserException("No inputs defined.");
	    }
	    if(this.primaryOutputs.size() == 0){
	    	throw new ParserException("No outputs defined.");
	    }
	    //sorting
	    Collections.sort(this.primaryInputs);
	    Collections.sort(this.primaryOutputs);
	}
	/**
	 * Constructs connection matrix
	 */
	protected void contructConnectionMatrix() throws ParserException{
		this.connectionNet = new Hashtable<CircuitEntity, List<String>>();
		
		//checking all entities
		Iterator<String> iterator = this.entities.keySet().iterator();
		while(iterator.hasNext()){
			String name = iterator.next();
			CircuitEntity entity = this.entities.get(name);
			String[] inputs = entity.inputs;
			
			for(int i = 0; i < inputs.length; i++){
				if(inputs[i].equals("")){ 
					continue;
				}
				CircuitEntity element = this.entities.get(inputs[i]);
				if(element == null){
					throw new ParserException("Entity " + entity.output + " has unconnected inputs.");
				}
				List<String> list = this.connectionNet.get(element);
				//if list doesn't exist
				if(list == null){
					list = new ArrayList<String>();
					this.connectionNet.put(this.entities.get(inputs[i]), list);
				}
				
				if(!(name.equals(element.output) && element instanceof Input)){
					list.add(name);
				}
			}
		}
	}
	
	/**
	 * Returns controllability of the gate
	 * @param gateName 	- name of the gate
	 * @param cc		- cc type 0/1
	 * @return controllability
	 */
	public int getCC(String gateName, boolean cc){
		int result = -1;
		CircuitEntity entity = this.entities.get(gateName);
		if(entity == null){
			return -1;
		}
		//if input
		if(entity instanceof Input){
			if(cc == true && entity.CC1 < 0){
				entity.CC1 = 1;
			}else if(cc == false && entity.CC1 < 0){
				entity.CC0 = 1;
			}
			if(cc == true){
				return entity.CC1;
			}else if(cc == false){
				return entity.CC0;
			}
		}
		//if gate
		if(entity instanceof Gate){
			Gate gate = (Gate)entity;
			//CC1
			if(cc == true && entity.CC1 > 0){
				return entity.CC1;
			}
			//CC0
			else if(cc == false && entity.CC0 > 0){
				return entity.CC0;
			}else{
				ArrayList<List<String>> variables = new  ArrayList<List<String>>();
			    ArrayList<List<Integer>> states = new ArrayList<List<Integer>>();
			    ArrayList<Integer> combinations = new ArrayList<Integer>();
			    gate.getCCInputs(variables, states, cc);
			    for(int i = 0; i < variables.size(); i++){
			    	List<String> vars = variables.get(i);
			    	List<Integer> ints = states.get(i);
			    	Integer sum = new Integer(0);
			    	int j = 0;
			    	Iterator<String> iterator = vars.iterator();
			    	while(iterator.hasNext()){
			    		String string = iterator.next();
			    		boolean ncc;
			    		if(ints.get(j) == 0){
			    			ncc = false;
			    		}else{
			    			ncc = true;
			    		}
			    		sum = new Integer(sum.intValue() + this.getCC(string, ncc));
			    		j++;
			    	}
			    	sum = new Integer(sum.intValue() + 1);
			    	combinations.add(sum);
			    }
			    int min = -1;
			    for(int i = 0; i < combinations.size(); i++){
			    	int value = combinations.get(i).intValue();
			    	if(min < 0 || value < min){
			    		min = value;
			    	}
			    }
			    result = min;
			    if(cc == true){
			    	entity.CC1 = result;
				}else if(cc == false){
					entity.CC0 = result;
				}
			}
		}
		return result;
	}
	/**
	 * Searches for a test for given fault
	 * @param fault name of faulty entity
	 * @param faultType s-a-0 or s-a-1
	 * @return
	 */
	public boolean findTest(String gate, String fault, LogicSystem faultType)throws Exception{
		//checking if the name of faulty entity is correct
		if(!this.entities.containsKey(gate)){
			throw new Exception();
		}
		if(!this.entities.containsKey(fault)){
			throw new Exception();
		}
		//checking if the faultType is correct
		if(!(faultType == LogicSystem.D || faultType == LogicSystem.notD)){
			throw new Exception();
		}
		
		//initializing the decision tree
		this.tree = new DecisionTree();
		for(String input : this.primaryInputs){
			tree.nodes.put(input, new DecisionNode(input));
		}
		
		
		//setting faulty gate
		CircuitEntity entity = this.entities.get(gate);
		entity.setFaulty();
		this.faulty = entity;
		this.fault = faultType;
		//fault on output
		if(gate.equals(fault)){
			//entity.outValue = faultType;
			//setting D-frontier
			List<String> list = this.connectionNet.get(entity);
			if(list == null)list = new ArrayList<String>();
			for(String element : list){
				CircuitEntity circuitElement = this.entities.get(element);
				int i = 0;
				for(String input : circuitElement.inputs){
					if(input.equals(fault) && !input.equals(circuitElement.output)){
						circuitElement.inValues[i] = faultType;
					}
					i++;
				}
				imply(element, circuitElement.inValues);
			}
		}else{
			boolean found = false;
			int i = 0;
			for(String input : entity.inputs){
				if(input.equals(fault)){
					found = true;
					entity.inValues[i] = faultType;
				}
				i++;
			}
			if(!found){
				throw new Exception();
			}
		}
		this.gut = this.faulty;
		
		boolean result = false;
		try{
			result = PODEMRecursion();
		}catch(Exception e){
			return false;
		}
		return result;
		//return true;
	}
	protected boolean PODEMRecursion() throws Exception{
		//is the fault observable at PO?
		if(gut.outValue == primaryObj && primaryObj != LogicSystem.X){
			
			if(this.verbose){System.out.println("Checking outputs.");}
			
			if(this.primaryOutputs.contains(gut.output)){
				gut.outValue = fault;
				return true;
			}
			for(String output : this.primaryOutputs){
				if(this.getEntity(output).outValue == LogicSystem.D || this.getEntity(output).outValue == LogicSystem.notD){
					return true;
				}
			}
		}
		Objective obj = getObjective();
		//no d frontier
		// obj.value == LogicSystem.X means here there's np d frontier
		
		if(obj.value == LogicSystem.X){
			
			if(this.verbose){System.out.println("Reorganizing the decision tree.");}
			
			//reorganizing the tree
			while(!tree.stack.isEmpty()){
				DecisionNode lastNode = tree.stack.peek();
				if(lastNode.isFlagged()){
					tree.stack.pop();
					lastNode.flag = false;
					CircuitEntity input = this.getEntity(lastNode.input);
					input.inValues[0] = LogicSystem.X;
					if(this.verbose){System.out.println("Setting input " + input.output + " " + LogicSystem.X);}
				}else{
					lastNode.setFlag();
					CircuitEntity input = this.getEntity(lastNode.input);
					input.inValues[0] = LogicSystem.NOT(input.inValues[0]);
					if(this.verbose){System.out.println("Setting input " + input.output + " " + input.inValues[0]);}
					break;
				}
			}
			
			if(tree.stack.isEmpty()){
				throw new Exception();
			}
			
			if(this.verbose){System.out.println("Forward implication");}
			forwardImplication();
			if(PODEMRecursion()){
				return true;
			}
		}else{
			if(this.verbose){System.out.println("Objective: set " + obj.entity.output + " to " + obj.value);}
		}
		
		if(this.verbose){System.out.println("Backtrace");}
		
		Objective u = new Objective(gut, LogicSystem.X);
		try{
			u = backtrace(obj);
		}catch(Exception e){
			e.printStackTrace();
			System.exit(1);
		}
		
		//if(this.verbose){System.out.println("End of backtrace.");}
		if(this.verbose){System.out.println("Setting input " + u.entity.output + " " + u.value);}
		
		//moving node to the stack and setting
		if(this.tree.nodes.containsKey(u.entity.output)){
			this.tree.stack.push(this.tree.nodes.get(u.entity.output));
			this.getEntity(u.entity.output).inValues[0] = u.value;
		}
		
		//forward implication
		if(this.verbose){System.out.println("Forward implication");}
		forwardImplication();
		
		if(PODEMRecursion()){
			return true;
		}
		
		return false;
	}
	protected Objective getObjective(){
		//FIGURE 8
		//gate under test
		//1
		
		//return new Objective(gut, LogicSystem.X);
		//means there is need to reorganize the decision
		
		//System.out.println("get objective");
		if(this.gut.outValue == LogicSystem.X){
			if(this.fault == LogicSystem.D){
				this.primaryObj = LogicSystem.TRUE;
				return new Objective(gut, LogicSystem.TRUE);
			}else{
				this.primaryObj = LogicSystem.FALSE;
				return new Objective(gut, LogicSystem.FALSE);
			}
		}else{
			//is the fault sensitized?
			if(this.gut.outValue != this.primaryObj){
				return new Objective(gut, LogicSystem.X);
			}
			dFrotier();
			
			//xPathCheck
			Iterator<String> iterator = dfrontier.iterator();
			while(iterator.hasNext()){
				String name = iterator.next();
				if(!xPathCheck(name)){
					iterator.remove();
				}
			}
			
			//selecting objective
			while(!dfrontier.isEmpty()){
				int index = 0;
				int min = -1;
				for(int i = 0; i < dfrontier.size(); i++){
					int distance = getDistanceToPO(dfrontier.get(i));
					if(distance < min || min < 0){
						min = distance;
						index = i;
					}
				}
				
				ArrayList<List<String>> variables = new  ArrayList<List<String>>();
			    ArrayList<List<Integer>> states = new ArrayList<List<Integer>>();
			    Gate g = (Gate)this.getEntity(dfrontier.get(index));
			    g.getCCInputs(variables, states, true);
			    
			    //all inputs need to be set
			    if(variables.get(0).size() == g.inputs.length){
			    	return new Objective(g, LogicSystem.TRUE);
			    }else{
			    	return new Objective(g, LogicSystem.FALSE);
			    }
			}
			if(dfrontier.isEmpty()){
				return new Objective(gut, LogicSystem.X);
			}
		}
		return new Objective(gut, LogicSystem.X);
	}
	
	/**
	 * Backtrace of given objective
	 * @param objective
	 * @return
	 */
	protected Objective backtrace(Objective objective){
		CircuitEntity i = objective.entity;
		boolean obj;
		boolean tempObj;
		if(objective.value == LogicSystem.TRUE){
			obj = true;
		}else{
			obj = false;
		}
		tempObj = obj;
		
		while(!(i instanceof Input)){
			obj = tempObj;
			//System.out.println("current objective: " + obj);
			if(i instanceof Gate){
				Gate ii = (Gate)i;
				//System.out.println("---------");
				//System.out.println(i.output);
				ArrayList<List<String>> variables = new  ArrayList<List<String>>();
			    ArrayList<List<Integer>> states = new ArrayList<List<Integer>>();
			    ii.getCCInputs(variables, states, obj);
			    //System.out.println(variables);
			    //System.out.println(states);
			    
			    //all inputs need to be set
			    if(variables.get(0).size() == ii.inputs.length){
			    	//System.out.println("all inputs required");
			    	//reducing possible combinations
			    	ArrayList<Integer> toRemove = new ArrayList<Integer>();
			    	for(int x = 0; x < states.size(); x++){
			    		List<Integer> combination = states.get(x);
			    		for(int y = 0; y < combination.size(); y++){
			    			if(ii.inValues[y] == LogicSystem.NOT(LogicSystem.fromInteger(combination.get(y).intValue()))){
			    				toRemove.add(new Integer(x));
			    				break;
			    			}
			    		}
			    	}
			    	//removing impossible combinations
			    	Collections.sort(toRemove);
			    	for(int z = toRemove.size()-1; z >= 0; z--){
			    		variables.remove(toRemove.get(z).intValue());
			    		states.remove(toRemove.get(z).intValue());
			    	}
			    	
				    Hashtable<String, List<Integer>> uInputs= new Hashtable<String, List<Integer>>(); 
				    //finding all inputs at X
				    for(int z = 0; z < ii.inputs.length; z++){
				    	if(ii.inValues[z] == LogicSystem.X){
				    		ArrayList<Integer> tmp = new ArrayList<Integer>();
				    		tmp.add(0);
				    		tmp.add(0);
				    		uInputs.put(ii.inputs[z], tmp);
				    	}
				    }
				    
				    //finding the highest controllability
				    Set<String> tmp = uInputs.keySet();
				    //System.out.println("-----------X-------------");
				    //System.out.println(tmp);
				    //System.out.println("-----------X-------------");
				    for(String name : tmp){
				    	for(int x = 0; x < variables.size(); x++){
				    		List<String> vars = variables.get(x);
				    		if(vars.contains(name)){
				    			int index = vars.indexOf(name);
				    			Integer state = states.get(x).get(index);
				    			boolean st;
				    			if(state.intValue() == 1){
				    				st = true;
				    			}else{
				    				st = false;
				    			}
				    			int controllability = getCC(name, st);
				    			List<Integer> contr = uInputs.get(name);
				    			if(contr.get(1).intValue() < controllability){
				    				ArrayList<Integer> newContr = new ArrayList<Integer>();
				    				newContr.add(controllability);
				    				newContr.add(state);
				    				uInputs.put(name, newContr);
				    			}
				    		}
				    	}
				    }
				    //System.out.println(uInputs);
				    String maxName = "";
				    int maxControllability = -1;
				    int maxState = -1;
				    for(String name : tmp){
				    	List<Integer> list = uInputs.get(name);	
				    	if(maxControllability < list.get(0).intValue()){
				    		maxName = name;
				    		maxControllability = list.get(0).intValue();
				    		maxState = list.get(1).intValue();
				    	}
				    }
				    
				    if(this.verbose){System.out.println("Current objective: set " + maxName + " to " + LogicSystem.fromInteger(maxState) + "(controllability:" + maxControllability+")");}
				    
				    i = this.getEntity(maxName);
				    if(maxState == 1){
				    	tempObj = true;
				    }else{
				    	tempObj = false;
				    }
			    }
			    //not all inputs need to be set
			    else{
			    	//System.out.println("not all need to be set");
			    	//reducing possible combinations
			    	ArrayList<Integer> toRemove = new ArrayList<Integer>();
			    	for(int x = 0; x < states.size(); x++){
			    		List<Integer> combination = states.get(x);
			    		List<String> names = variables.get(x);
			    		for(int y = 0; y < combination.size(); y++){
			    			String name = names.get(y);
			    			int index = 0;
			    			for(int z = 0; z < ii.inputs.length; z++){
			    				if(ii.inputs[z].equals(name)){
			    					index = z;
			    					break;
			    				}
			    			}
			    			if(ii.inValues[index] == LogicSystem.NOT(LogicSystem.fromInteger(combination.get(y).intValue()))){
			    				toRemove.add(new Integer(x));
			    				break;
			    			}
			    		}
			    	}
			    	//removing impossible combinations
			    	Collections.sort(toRemove);
			    	for(int z = toRemove.size()-1; z >= 0; z--){
			    		variables.remove(toRemove.get(z).intValue());
			    		states.remove(toRemove.get(z).intValue());
			    	}
			    	
				    Hashtable<String, List<Integer>> uInputs= new Hashtable<String, List<Integer>>();
				    //finding all inputs at X
				    for(int z = 0; z < ii.inputs.length; z++){
				    	if(ii.inValues[z] == LogicSystem.X){
				    		ArrayList<Integer> tmp = new ArrayList<Integer>();
				    		tmp.add(0);
				    		tmp.add(0);
				    		uInputs.put(ii.inputs[z], tmp);
				    	}
				    }
				    
				  //finding the lowest controllability
				    Set<String> tmp = uInputs.keySet();
				    for(String name : tmp){
				    	for(int x = 0; x < variables.size(); x++){
				    		List<String> vars = variables.get(x);
				    		if(vars.contains(name)){
				    			int index = vars.indexOf(name);
				    			Integer state = states.get(x).get(index);
				    			boolean st;
				    			if(state.intValue() == 1){
				    				st = true;
				    			}else{
				    				st = false;
				    			}
				    			int controllability = getCC(name, st);
				    			List<Integer> contr = uInputs.get(name);
				    			if(contr.get(1).intValue() > controllability || contr.get(1).intValue() <= 0){
				    				ArrayList<Integer> newContr = new ArrayList<Integer>();
				    				newContr.add(controllability);
				    				newContr.add(state);
				    				uInputs.put(name, newContr);
				    			}
				    		}
				    	}
				    }
				    
				    //System.out.println(uInputs);
				    String minName = "";
				    int minControllability = -1;
				    int minState = -1;
				    for(String name : tmp){
				    	List<Integer> list = uInputs.get(name);	
				    	if(minControllability < 0 || minControllability > list.get(0).intValue()){
				    		minName = name;
				    		minControllability = list.get(0).intValue();
				    		minState = list.get(1).intValue();
				    	}
				    }
				    //System.out.println(minName + " " + minControllability + " " + minState);
				    i = this.getEntity(minName);
				    if(minState == 1){
				    	tempObj = true;
				    }else{
				    	tempObj = false;
				    }

			    }			    
			}
		}
		return new Objective(i, LogicSystem.fromBoolean(tempObj));
	}
	
	/**
	 * Implication starting from entity with "name" and setting its "inputs"
	 * @param name		name of the entity to start with
	 * @param inputs	input vector
	 * @return
	 */
	protected boolean imply(String name, LogicSystem[] inputs){
		CircuitEntity entity = this.getEntity(name);
		entity.inValues = inputs;
		LogicSystem result = entity.evaluate(inputs);
		//System.out.println(name + " " + result);
		if(result == entity.outValue){
			return false;
		}else{
			entity.outValue = result;
			List<String> children = this.connectionNet.get(entity);
			if(children != null){
				for(String child : children){
					CircuitEntity childEntity = this.getEntity(child);
					int index = 0;
					for(int i = 0; i < childEntity.inputs.length; i++){
						if(childEntity.inputs[i].equals(name)){
							index = i;
							break;
						}
					}
					if(entity.isFaulty()){
						childEntity.inValues[index] = this.fault;
					}else{
						childEntity.inValues[index] = result;
					}
					imply(child, childEntity.inValues);
				}
			}
			return true;
		}
	}
	
	/**
	 * Forward implication (implication starting from primary inputs)
	 * @return
	 */
	protected boolean forwardImplication(){
		for(String input : this.primaryInputs){
			CircuitEntity PI = this.getEntity(input);
			imply(input, PI.inValues);
		}
		return true;
	}
	
	protected void dFrotier(){
		//clearing d frontier
		this.dfrontier = new ArrayList<String>();
		//looking for d frontier gates
		for(String entity : this.entities.keySet()){
			CircuitEntity circuitEntity = this.entities.get(entity);
			if(circuitEntity.outValue == LogicSystem.X){
				boolean foundx = false;
				boolean foundd = false;
				for(LogicSystem input : circuitEntity.inValues){
					if(input == LogicSystem.X){
						foundx = true;
					}else if(input == LogicSystem.D || input == LogicSystem.notD){
						foundd = true;
					}
				}
				if(foundx && foundd){
					this.dfrontier.add(entity);
				}
			}
		}
	}
	public int getDistanceToPO(String name){
		CircuitEntity entity = this.getEntity(name);
		if(entity.distanceToPO != -1){
			return entity.distanceToPO;
		}
		if(this.primaryOutputs.contains(name)){
			entity.distanceToPO = 0;
			return 0;
		}else{
			List<String> children = this.connectionNet.get(entity);
			ArrayList<Integer> distances = new ArrayList<Integer>();
			for(String child : children){
				distances.add(new Integer(getDistanceToPO(child)));
			}
			int min = -1;
			for(int i = 0; i < distances.size(); i++){
				if(distances.get(i).intValue() < min || min < 0){
					min = distances.get(i).intValue();
				}
			}
			entity.distanceToPO = min;
			return min;
		}
	}
	
	protected boolean xPathCheck(String name){
		CircuitEntity entity = this.getEntity(name);
		if(this.primaryOutputs.contains(name) && entity.outValue == LogicSystem.X){
			return true;
		}
		if(entity.outValue != LogicSystem.X){
			return false;
		}else{
			List<String> children = this.connectionNet.get(entity);
			for(String child : children){
				if(xPathCheck(child)){
					return true;
				}
			}
			return false;
		}
	}
	
	/**
	 * returns current state of inputs in printable form
	 * @return
	 */
	public String inputsToString(){
		String string = new String();
		for(int i = 0; i < this.primaryInputs.size(); i++){
			string += this.primaryInputs.get(i) + "\t";
		}
		string += "\n";
		for(int i = 0; i < this.primaryInputs.size(); i++){
			CircuitEntity entity = this.entities.get(this.primaryInputs.get(i));
			string += entity.inValues[0] + "\t";
		}
		return string;
	}
	
	/**
	 * returns current state of outputs in printable form
	 * @return
	 */
	public String outputsToString(){
		String string = new String();
		for(int i = 0; i < this.primaryOutputs.size(); i++){
			string += this.primaryOutputs.get(i) + "\t";
		}
		string += "\n";
		for(int i = 0; i < this.primaryOutputs.size(); i++){
			CircuitEntity entity = this.entities.get(this.primaryOutputs.get(i));
			string += entity.outValue + "\t";
		}
		return string;
	}

}
